// bzoj1097
// 题意：给定n(<=20000)个点，m(<=200000)条无向边的带权图，现在一定要
//       经过k(<=20)个点，这k个点是2, 3, ..., k + 1，并且给出了
//       q(<=k*(k-1)/2)条限制关系，表示这k个点中某个点一定要在k个点中另一个
//       点之前访问。问从1开始经过k个点（满足题目限制）到n结束，最小的
//       花费。
//
// 题解：先算出k个点到别的点的最短路。然后状态压缩。dp[st][j]表示状态st下，
//       以j结尾的最小费用。要先预处理出那个拓扑限制的关系，然后边界情况
//       也要注意，比如k=0。我很想知道bzoj上第一名的算法是什么...
//
// run: $exec < input
// opt: 0
// flag: -g
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

int const maxn = 20007;
int const maxm = 200007 * 2;
int head[maxn], end[maxm], next[maxm], cost[maxm];
int alloc = 2;
int n, m, k;

struct node { int to, cost; };

int const inf = 1 << 29;

void dijkstra(int source, std::vector<int> & dist)
{
	dist.resize(n);
	std::fill(dist.begin(), dist.end(), inf);
	dist[source] = 0;
	typedef std::pair<int, int> cost_end;
	std::priority_queue<cost_end, std::vector<cost_end>, std::greater<cost_end> > pq;
	pq.push(std::make_pair(0, source));
	while (!pq.empty()) {
		cost_end tmp = pq.top(); pq.pop();
		int u = tmp.second;
		if (dist[u] < tmp.first) continue;

		for (int p = head[u]; p; p = next[p]) {
			int v = end[p], c = cost[p];
			if (dist[v] > dist[u] + c) {
				dist[v] = dist[u] + c;
				pq.push(std::make_pair(dist[v], v));
			}
		}
	}
}

std::vector<std::vector<int> > dist;

void add_edge(int u, int v, int c)
{
	end[alloc] = v; cost[alloc] = c; next[alloc] = head[u]; head[u] = alloc++;
	end[alloc] = u; cost[alloc] = c; next[alloc] = head[v]; head[v] = alloc++;
}

int q;
int head2[30], end2[900], next2[900], alloc2 = 2;
bool must[30][30];

void add_edge2(int u, int v)
{
	end2[alloc2] = v; next2[alloc2] = head2[u]; head2[u] = alloc2++;
}

void dfs(int u, int s)
{
	for (int p = head2[u]; p; p = next2[p]) {
		int v = end2[p];
		must[s][v] = true;
		dfs(v, s);
	}
}

int dis[1 << 21][22];

int main()
{
	std::scanf("%d%d%d", &n, &m, &k);
	for (int i = 0, x, y, z; i < m; i++) {
		std::scanf("%d%d%d", &x, &y, &z);
		add_edge(--x, --y, z);
	}
	dist.resize(k + 1);
	for (int i = 0; i <= k; i++) dijkstra(i, dist[i]);

	std::scanf("%d", &q);
	for (int i = 0, x, y; i < q; i++) {
		std::scanf("%d%d", &x, &y);
		add_edge2(--x, --y);
	}
	for (int i = 1; i <= k; i++) dfs(i, i);

	if (!k) {
		std::printf("%d\n", dist[0][n - 1]);
		return 0;
	}

	std::memset(dis, -1, sizeof(dis));
	for (int i = 1; i < (1 << k); i++) {
		for (int j = 0; j < k; j++) {
			int tmp = inf;
			if (!((i >> j) & 1)) continue;
			int ti = i ^ (1 << j);
			if (!ti) {
				dis[i][j + 1] = dist[0][j + 1];
				continue;
			}
			bool can = true;
			for (int t = 0; t < k; t++) {
				if (!((ti >> t) & 1)) continue;
				if (must[j + 1][t + 1]) {
					can = false; break;
				}
			}
			if (!can) continue;
			for (int t = 0; t < k; t++) {
				if (!(((ti >> t) & 1))) continue;
				if (dis[ti][t + 1] == -1) continue;
				tmp = std::min(tmp, dis[ti][t + 1] + dist[t + 1][j + 1]);
			}
			dis[i][j + 1] = tmp;
		}
	}
	int ans = inf;
	int pos = 0;
	for (int i = 1; i <= k; i++) {
		if (dis[(1 << k) - 1][i] == -1) continue;
		if (dis[(1 << k) - 1][i] + dist[i][n - 1] < ans) {
			pos = i;
		}
		ans = std::min(ans, dis[(1 << k) - 1][i] + dist[i][n - 1]);
	}

	std::printf("%d\n", ans);
}

